package com.zlk.algorithm.dataStructure.tree.serialize;

import com.zlk.algorithm.dataStructure.tree.NodeUtils;
import com.zlk.algorithm.dataStructure.tree.TreeNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @program: algorithm
 * @ClassName SerializeAndReconstructTree
 * @description:  二叉树序列化与反序列化  todo
 * @author: slfang
 * @create: 2024-02-22 09:52
 * @Version 1.0
 **/
public class SerializeAndReconstructTree {


    /*
     * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
     * 以下代码全部实现了。
     * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
     * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
     * 比如如下两棵树
     *         __2
     *        /
     *       1
     *       和
     *       1__
     *          \
     *           2
     * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
     *
     * */

    /**
     * 先序序列化
     * @param node
     * @return
     */
    public Queue<String> preSerial(TreeNode node){
        Queue<String> queue= new LinkedList<>();
        preSerial(node,queue);
        return queue;

    }

    private void preSerial(TreeNode head, Queue<String> ans) {
        if(head == null){
            ans.add(null);
        }else{
            ans.add(String.valueOf(head.value));
            preSerial(head.left,ans);
            preSerial(head.right,ans);
        }
    }

    public static Queue<String> posSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        poss(head, ans);
        return ans;
    }

    public static void poss(TreeNode head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            poss(head.left, ans);
            poss(head.right, ans);
            ans.add(String.valueOf(head.value));
        }
    }

    /**
     * 先序反序列化
     * @param prelist
     * @return
     */
    public TreeNode buildByPreQueue(Queue<String> prelist) {
        TreeNode head = null;
        if(prelist.size()==0||prelist==null){
            return null;
        }
        return preb(prelist);
    }

    /**
     *
     * @param prelist
     * @return
     */
    public TreeNode preb(Queue<String> prelist) {
        String poll = prelist.poll();
        if (poll == null) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(poll));
        node.left =preb(prelist);
        node.right =preb(prelist);
        return node;
    }



    //          1
    //    2           3
    //  4           5
    //
    public TreeNode buildByPosQueue(Queue<String> poslist) {
        if (poslist == null || poslist.size() == 0) {
            return null;
        }
        // 左右中  ->  stack(中右左)
        Stack<String> stack = new Stack<>();
        for (String s : poslist) {
            stack.push(s);
        }
        return posb(stack);
    }

    private TreeNode posb(Stack<String> stack) {
        String pop = stack.pop();
        if(pop==null){
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(pop));
        node.right = posb(stack);
        node.left = posb(stack);
        return node;
    }

    public static Queue<String> levelSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(String.valueOf(head.value));
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(head);
            while (!queue.isEmpty()) {
                head = queue.poll(); // head 父   子
                if (head.left != null) {
                    ans.add(String.valueOf(head.left.value));
                    queue.add(head.left);
                } else {
                    ans.add(null);
                }
                if (head.right != null) {
                    ans.add(String.valueOf(head.right.value));
                    queue.add(head.right);
                } else {
                    ans.add(null);
                }
            }
        }
        return ans;
    }


    //todo
    public  TreeNode buildByLevelQueue(Queue<String> levelList) {
        if (levelList == null || levelList.size() == 0) {
            return null;
        }
        TreeNode head = generateNode(levelList.poll());
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (head != null) {
            queue.add(head);
        }
        TreeNode node = null;
        while (!queue.isEmpty()){
            node = queue.poll();
            node.left = generateNode(levelList.poll());
            node.right = generateNode(levelList.poll());
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return head;
    }

    public static TreeNode generateNode(String val) {
        if (val == null) {
            return null;
        }
        return new TreeNode(Integer.valueOf(val));
    }

    public  boolean isSameValueStructure(TreeNode head1, TreeNode head2) {
        if (head1 == null && head2 != null) {
            return false;
        }
        if (head1 != null && head2 == null) {
            return false;
        }
        if (head1 == null && head2 == null) {
            return true;
        }
        if (head1.value != head2.value) {
            return false;
        }
        return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
    }
    @Test
    public void test(){
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = NodeUtils.generateRandomBST(maxLevel, maxValue);
            Queue<String> pre = preSerial(head);
            Queue<String> pos = posSerial(head);
            Queue<String> level = levelSerial(head);
            TreeNode preBuild = buildByPreQueue(pre);
            TreeNode posBuild = buildByPosQueue(pos);
            TreeNode levelBuild = buildByLevelQueue(level);
            if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish!");
    }



}
